<!doctype html>
<html>
<head>
<meta charset='UTF-8'><meta name='viewport' content='width=device-width initial-scale=1'>
<link href="/css/bootstrap.min.css" rel="stylesheet">
<!-- style sheet of Vssue -->
<link rel="stylesheet" href="https://unpkg.com/vssue/dist/vssue.min.css">
<script src="https://code.jquery.com/jquery-3.6.0.min.js" integrity="sha256-/xUj+3OJU5yExlq6GSYGSHk7tPXikynS7ogEvDej/m4=" crossorigin="anonymous"></script>

<script src="https://unpkg.com/vue/dist/vue.min.js"></script>
<script src="https://unpkg.com/vssue/dist/vssue.gitee.min.js"></script>
<link href='https://fonts.loli.net/css?family=Open+Sans:400italic,700italic,700,400&subset=latin,latin-ext' rel='stylesheet' type='text/css' /><style type='text/css'>html {overflow-x: initial !important;}:root { --bg-color:#ffffff; --text-color:#333333; --select-text-bg-color:#B5D6FC; --select-text-font-color:auto; --monospace:"Lucida Console",Consolas,"Courier",monospace; --title-bar-height:20px; }
.mac-os-11 { --title-bar-height:28px; }
html { font-size: 14px; background-color: var(--bg-color); color: var(--text-color); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; -webkit-font-smoothing: antialiased; }
body { margin: 0px; padding: 0px; height: auto; inset: 0px; font-size: 1rem; line-height: 1.42857; overflow-x: hidden; background: inherit; tab-size: 4; }
iframe { margin: auto; }
a.url { word-break: break-all; }
a:active, a:hover { outline: 0px; }
.in-text-selection, ::selection { text-shadow: none; background: var(--select-text-bg-color); color: var(--select-text-font-color); }
#write { margin: 0px auto; height: auto; width: inherit; word-break: normal; overflow-wrap: break-word; position: relative; white-space: normal; overflow-x: visible; padding-top: 36px; }
#write.first-line-indent p { text-indent: 2em; }
#write.first-line-indent li p, #write.first-line-indent p * { text-indent: 0px; }
#write.first-line-indent li { margin-left: 2em; }
.for-image #write { padding-left: 8px; padding-right: 8px; }
body.typora-export { padding-left: 30px; padding-right: 30px; }
.typora-export .footnote-line, .typora-export li, .typora-export p { white-space: pre-wrap; }
.typora-export .task-list-item input { pointer-events: none; }
@media screen and (max-width: 500px) {
  body.typora-export { padding-left: 0px; padding-right: 0px; }
  #write { padding-left: 20px; padding-right: 20px; }
  .CodeMirror-sizer { margin-left: 0px !important; }
  .CodeMirror-gutters { display: none !important; }
}
#write li > figure:last-child { margin-bottom: 0.5rem; }
#write ol, #write ul { position: relative; }
img { max-width: 100%; vertical-align: middle; image-orientation: from-image; }
button, input, select, textarea { color: inherit; font: inherit; }
input[type="checkbox"], input[type="radio"] { line-height: normal; padding: 0px; }
*, ::after, ::before { box-sizing: border-box; }
#write h1, #write h2, #write h3, #write h4, #write h5, #write h6, #write p, #write pre { width: inherit; }
#write h1, #write h2, #write h3, #write h4, #write h5, #write h6, #write p { position: relative; }
p { line-height: inherit; }
h1, h2, h3, h4, h5, h6 { break-after: avoid-page; break-inside: avoid; orphans: 4; }
p { orphans: 4; }
h1 { font-size: 2rem; }
h2 { font-size: 1.8rem; }
h3 { font-size: 1.6rem; }
h4 { font-size: 1.4rem; }
h5 { font-size: 1.2rem; }
h6 { font-size: 1rem; }
.md-math-block, .md-rawblock, h1, h2, h3, h4, h5, h6, p { margin-top: 1rem; margin-bottom: 1rem; }
.hidden { display: none; }
.md-blockmeta { color: rgb(204, 204, 204); font-weight: 700; font-style: italic; }
a { cursor: pointer; }
sup.md-footnote { padding: 2px 4px; background-color: rgba(238, 238, 238, 0.7); color: rgb(85, 85, 85); border-radius: 4px; cursor: pointer; }
sup.md-footnote a, sup.md-footnote a:hover { color: inherit; text-transform: inherit; text-decoration: inherit; }
#write input[type="checkbox"] { cursor: pointer; width: inherit; height: inherit; }
figure { overflow-x: auto; margin: 1.2em 0px; max-width: calc(100% + 16px); padding: 0px; }
figure > table { margin: 0px; }
tr { break-inside: avoid; break-after: auto; }
thead { display: table-header-group; }
table { border-collapse: collapse; border-spacing: 0px; width: 100%; overflow: auto; break-inside: auto; text-align: left; }
table.md-table td { min-width: 32px; }
.CodeMirror-gutters { border-right: 0px; background-color: inherit; }
.CodeMirror-linenumber { user-select: none; }
.CodeMirror { text-align: left; }
.CodeMirror-placeholder { opacity: 0.3; }
.CodeMirror pre { padding: 0px 4px; }
.CodeMirror-lines { padding: 0px; }
div.hr:focus { cursor: none; }
#write pre { white-space: pre-wrap; }
#write.fences-no-line-wrapping pre { white-space: pre; }
#write pre.ty-contain-cm { white-space: normal; }
.CodeMirror-gutters { margin-right: 4px; }
.md-fences { font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; overflow: visible; white-space: pre; background: inherit; position: relative !important; }
.md-fences-adv-panel { width: 100%; margin-top: 10px; text-align: center; padding-top: 0px; padding-bottom: 8px; overflow-x: auto; }
#write .md-fences.mock-cm { white-space: pre-wrap; }
.md-fences.md-fences-with-lineno { padding-left: 0px; }
#write.fences-no-line-wrapping .md-fences.mock-cm { white-space: pre; overflow-x: auto; }
.md-fences.mock-cm.md-fences-with-lineno { padding-left: 8px; }
.CodeMirror-line, twitterwidget { break-inside: avoid; }
.footnotes { opacity: 0.8; font-size: 0.9rem; margin-top: 1em; margin-bottom: 1em; }
.footnotes + .footnotes { margin-top: 0px; }
.md-reset { margin: 0px; padding: 0px; border: 0px; outline: 0px; vertical-align: top; background: 0px 0px; text-decoration: none; text-shadow: none; float: none; position: static; width: auto; height: auto; white-space: nowrap; cursor: inherit; -webkit-tap-highlight-color: transparent; line-height: normal; font-weight: 400; text-align: left; box-sizing: content-box; direction: ltr; }
li div { padding-top: 0px; }
blockquote { margin: 1rem 0px; }
li .mathjax-block, li p { margin: 0.5rem 0px; }
li blockquote { margin: 1rem 0px; }
li { margin: 0px; position: relative; }
blockquote > :last-child { margin-bottom: 0px; }
blockquote > :first-child, li > :first-child { margin-top: 0px; }
.footnotes-area { color: rgb(136, 136, 136); margin-top: 0.714rem; padding-bottom: 0.143rem; white-space: normal; }
#write .footnote-line { white-space: pre-wrap; }
@media print {
  body, html { border: 1px solid transparent; height: 99%; break-after: avoid; break-before: avoid; font-variant-ligatures: no-common-ligatures; }
  #write { margin-top: 0px; padding-top: 0px; border-color: transparent !important; }
  .typora-export * { -webkit-print-color-adjust: exact; }
  .typora-export #write { break-after: avoid; }
  .typora-export #write::after { height: 0px; }
  .is-mac table { break-inside: avoid; }
  .typora-export-show-outline .typora-export-sidebar { display: none; }
}
.footnote-line { margin-top: 0.714em; font-size: 0.7em; }
a img, img a { cursor: pointer; }
pre.md-meta-block { font-size: 0.8rem; min-height: 0.8rem; white-space: pre-wrap; background: rgb(204, 204, 204); display: block; overflow-x: hidden; }
p > .md-image:only-child:not(.md-img-error) img, p > img:only-child { display: block; margin: auto; }
#write.first-line-indent p > .md-image:only-child:not(.md-img-error) img { left: -2em; position: relative; }
p > .md-image:only-child { display: inline-block; width: 100%; }
#write .MathJax_Display { margin: 0.8em 0px 0px; }
.md-math-block { width: 100%; }
.md-math-block:not(:empty)::after { display: none; }
.MathJax_ref { fill: currentcolor; }
[contenteditable="true"]:active, [contenteditable="true"]:focus, [contenteditable="false"]:active, [contenteditable="false"]:focus { outline: 0px; box-shadow: none; }
.md-task-list-item { position: relative; list-style-type: none; }
.task-list-item.md-task-list-item { padding-left: 0px; }
.md-task-list-item > input { position: absolute; top: 0px; left: 0px; margin-left: -1.2em; margin-top: calc(1em - 10px); border: none; }
.math { font-size: 1rem; }
.md-toc { min-height: 3.58rem; position: relative; font-size: 0.9rem; border-radius: 10px; }
.md-toc-content { position: relative; margin-left: 0px; }
.md-toc-content::after, .md-toc::after { display: none; }
.md-toc-item { display: block; color: rgb(65, 131, 196); }
.md-toc-item a { text-decoration: none; }
.md-toc-inner:hover { text-decoration: underline; }
.md-toc-inner { display: inline-block; cursor: pointer; }
.md-toc-h1 .md-toc-inner { margin-left: 0px; font-weight: 700; }
.md-toc-h2 .md-toc-inner { margin-left: 2em; }
.md-toc-h3 .md-toc-inner { margin-left: 4em; }
.md-toc-h4 .md-toc-inner { margin-left: 6em; }
.md-toc-h5 .md-toc-inner { margin-left: 8em; }
.md-toc-h6 .md-toc-inner { margin-left: 10em; }
@media screen and (max-width: 48em) {
  .md-toc-h3 .md-toc-inner { margin-left: 3.5em; }
  .md-toc-h4 .md-toc-inner { margin-left: 5em; }
  .md-toc-h5 .md-toc-inner { margin-left: 6.5em; }
  .md-toc-h6 .md-toc-inner { margin-left: 8em; }
}
a.md-toc-inner { font-size: inherit; font-style: inherit; font-weight: inherit; line-height: inherit; }
.footnote-line a:not(.reversefootnote) { color: inherit; }
.md-attr { display: none; }
.md-fn-count::after { content: "."; }
code, pre, samp, tt { font-family: var(--monospace); }
kbd { margin: 0px 0.1em; padding: 0.1em 0.6em; font-size: 0.8em; color: rgb(36, 39, 41); background: rgb(255, 255, 255); border: 1px solid rgb(173, 179, 185); border-radius: 3px; box-shadow: rgba(12, 13, 14, 0.2) 0px 1px 0px, rgb(255, 255, 255) 0px 0px 0px 2px inset; white-space: nowrap; vertical-align: middle; }
.md-comment { color: rgb(162, 127, 3); opacity: 0.6; font-family: var(--monospace); }
code { text-align: left; vertical-align: initial; }
a.md-print-anchor { white-space: pre !important; border-width: initial !important; border-style: none !important; border-color: initial !important; display: inline-block !important; position: absolute !important; width: 1px !important; right: 0px !important; outline: 0px !important; background: 0px 0px !important; text-decoration: initial !important; text-shadow: initial !important; }
.os-windows.monocolor-emoji .md-emoji { font-family: "Segoe UI Symbol", sans-serif; }
.md-diagram-panel > svg { max-width: 100%; }
[lang="flow"] svg, [lang="mermaid"] svg { max-width: 100%; height: auto; }
[lang="mermaid"] .node text { font-size: 1rem; }
table tr th { border-bottom: 0px; }
video { max-width: 100%; display: block; margin: 0px auto; }
iframe { max-width: 100%; width: 100%; border: none; }
.highlight td, .highlight tr { border: 0px; }
mark { background: rgb(255, 255, 0); color: rgb(0, 0, 0); }
.md-html-inline .md-plain, .md-html-inline strong, mark .md-inline-math, mark strong { color: inherit; }
.md-expand mark .md-meta { opacity: 0.3 !important; }
mark .md-meta { color: rgb(0, 0, 0); }
@media print {
  .typora-export h1, .typora-export h2, .typora-export h3, .typora-export h4, .typora-export h5, .typora-export h6 { break-inside: avoid; }
}
.md-diagram-panel .messageText { stroke: none !important; }
.md-diagram-panel .start-state { fill: var(--node-fill); }
.md-diagram-panel .edgeLabel rect { opacity: 1 !important; }
.md-fences.md-fences-math { font-size: 1em; }
.md-fences-advanced:not(.md-focus) { padding: 0px; white-space: nowrap; border: 0px; }
.md-fences-advanced:not(.md-focus) { background: inherit; }
.typora-export-show-outline .typora-export-content { max-width: 1440px; margin: auto; display: flex; flex-direction: row; }
.typora-export-sidebar { width: 300px; font-size: 0.8rem; margin-top: 80px; margin-right: 18px; }
.typora-export-show-outline #write { --webkit-flex:2; flex: 2 1 0%; }
.typora-export-sidebar .outline-content { position: fixed; top: 0px; max-height: 100%; overflow: hidden auto; padding-bottom: 30px; padding-top: 60px; width: 300px; }
@media screen and (max-width: 1024px) {
  .typora-export-sidebar, .typora-export-sidebar .outline-content { width: 240px; }
}
@media screen and (max-width: 800px) {
  .typora-export-sidebar { display: none; }
}
.outline-content li, .outline-content ul { margin-left: 0px; margin-right: 0px; padding-left: 0px; padding-right: 0px; list-style: none; }
.outline-content ul { margin-top: 0px; margin-bottom: 0px; }
.outline-content strong { font-weight: 400; }
.outline-expander { width: 1rem; height: 1.42857rem; position: relative; display: table-cell; vertical-align: middle; cursor: pointer; padding-left: 4px; }
.outline-expander::before { content: ""; position: relative; font-family: Ionicons; display: inline-block; font-size: 8px; vertical-align: middle; }
.outline-item { padding-top: 3px; padding-bottom: 3px; cursor: pointer; }
.outline-expander:hover::before { content: ""; }
.outline-h1 > .outline-item { padding-left: 0px; }
.outline-h2 > .outline-item { padding-left: 1em; }
.outline-h3 > .outline-item { padding-left: 2em; }
.outline-h4 > .outline-item { padding-left: 3em; }
.outline-h5 > .outline-item { padding-left: 4em; }
.outline-h6 > .outline-item { padding-left: 5em; }
.outline-label { cursor: pointer; display: table-cell; vertical-align: middle; text-decoration: none; color: inherit; }
.outline-label:hover { text-decoration: underline; }
.outline-item:hover { border-color: rgb(245, 245, 245); background-color: var(--item-hover-bg-color); }
.outline-item:hover { margin-left: -28px; margin-right: -28px; border-left: 28px solid transparent; border-right: 28px solid transparent; }
.outline-item-single .outline-expander::before, .outline-item-single .outline-expander:hover::before { display: none; }
.outline-item-open > .outline-item > .outline-expander::before { content: ""; }
.outline-children { display: none; }
.info-panel-tab-wrapper { display: none; }
.outline-item-open > .outline-children { display: block; }
.typora-export .outline-item { padding-top: 1px; padding-bottom: 1px; }
.typora-export .outline-item:hover { margin-right: -8px; border-right: 8px solid transparent; }
.typora-export .outline-expander::before { content: "+"; font-family: inherit; top: -1px; }
.typora-export .outline-expander:hover::before, .typora-export .outline-item-open > .outline-item > .outline-expander::before { content: "−"; }
.typora-export-collapse-outline .outline-children { display: none; }
.typora-export-collapse-outline .outline-item-open > .outline-children, .typora-export-no-collapse-outline .outline-children { display: block; }
.typora-export-no-collapse-outline .outline-expander::before { content: "" !important; }
.typora-export-show-outline .outline-item-active > .outline-item .outline-label { font-weight: 700; }
.md-inline-math-container mjx-container { zoom: 0.95; }


.CodeMirror { height: auto; }
.CodeMirror.cm-s-inner { background: inherit; }
.CodeMirror-scroll { overflow: auto hidden; z-index: 3; }
.CodeMirror-gutter-filler, .CodeMirror-scrollbar-filler { background-color: rgb(255, 255, 255); }
.CodeMirror-gutters { border-right: 1px solid rgb(221, 221, 221); background: inherit; white-space: nowrap; }
.CodeMirror-linenumber { padding: 0px 3px 0px 5px; text-align: right; color: rgb(153, 153, 153); }
.cm-s-inner .cm-keyword { color: rgb(119, 0, 136); }
.cm-s-inner .cm-atom, .cm-s-inner.cm-atom { color: rgb(34, 17, 153); }
.cm-s-inner .cm-number { color: rgb(17, 102, 68); }
.cm-s-inner .cm-def { color: rgb(0, 0, 255); }
.cm-s-inner .cm-variable { color: rgb(0, 0, 0); }
.cm-s-inner .cm-variable-2 { color: rgb(0, 85, 170); }
.cm-s-inner .cm-variable-3 { color: rgb(0, 136, 85); }
.cm-s-inner .cm-string { color: rgb(170, 17, 17); }
.cm-s-inner .cm-property { color: rgb(0, 0, 0); }
.cm-s-inner .cm-operator { color: rgb(152, 26, 26); }
.cm-s-inner .cm-comment, .cm-s-inner.cm-comment { color: rgb(170, 85, 0); }
.cm-s-inner .cm-string-2 { color: rgb(255, 85, 0); }
.cm-s-inner .cm-meta { color: rgb(85, 85, 85); }
.cm-s-inner .cm-qualifier { color: rgb(85, 85, 85); }
.cm-s-inner .cm-builtin { color: rgb(51, 0, 170); }
.cm-s-inner .cm-bracket { color: rgb(153, 153, 119); }
.cm-s-inner .cm-tag { color: rgb(17, 119, 0); }
.cm-s-inner .cm-attribute { color: rgb(0, 0, 204); }
.cm-s-inner .cm-header, .cm-s-inner.cm-header { color: rgb(0, 0, 255); }
.cm-s-inner .cm-quote, .cm-s-inner.cm-quote { color: rgb(0, 153, 0); }
.cm-s-inner .cm-hr, .cm-s-inner.cm-hr { color: rgb(153, 153, 153); }
.cm-s-inner .cm-link, .cm-s-inner.cm-link { color: rgb(0, 0, 204); }
.cm-negative { color: rgb(221, 68, 68); }
.cm-positive { color: rgb(34, 153, 34); }
.cm-header, .cm-strong { font-weight: 700; }
.cm-del { text-decoration: line-through; }
.cm-em { font-style: italic; }
.cm-link { text-decoration: underline; }
.cm-error { color: red; }
.cm-invalidchar { color: red; }
.cm-constant { color: rgb(38, 139, 210); }
.cm-defined { color: rgb(181, 137, 0); }
div.CodeMirror span.CodeMirror-matchingbracket { color: rgb(0, 255, 0); }
div.CodeMirror span.CodeMirror-nonmatchingbracket { color: rgb(255, 34, 34); }
.cm-s-inner .CodeMirror-activeline-background { background: inherit; }
.CodeMirror { position: relative; overflow: hidden; }
.CodeMirror-scroll { height: 100%; outline: 0px; position: relative; box-sizing: content-box; background: inherit; }
.CodeMirror-sizer { position: relative; }
.CodeMirror-gutter-filler, .CodeMirror-hscrollbar, .CodeMirror-scrollbar-filler, .CodeMirror-vscrollbar { position: absolute; z-index: 6; display: none; outline: 0px; }
.CodeMirror-vscrollbar { right: 0px; top: 0px; overflow: hidden; }
.CodeMirror-hscrollbar { bottom: 0px; left: 0px; overflow: auto hidden; }
.CodeMirror-scrollbar-filler { right: 0px; bottom: 0px; }
.CodeMirror-gutter-filler { left: 0px; bottom: 0px; }
.CodeMirror-gutters { position: absolute; left: 0px; top: 0px; padding-bottom: 10px; z-index: 3; overflow-y: hidden; }
.CodeMirror-gutter { white-space: normal; height: 100%; box-sizing: content-box; padding-bottom: 30px; margin-bottom: -32px; display: inline-block; }
.CodeMirror-gutter-wrapper { position: absolute; z-index: 4; background: 0px 0px !important; border: none !important; }
.CodeMirror-gutter-background { position: absolute; top: 0px; bottom: 0px; z-index: 4; }
.CodeMirror-gutter-elt { position: absolute; cursor: default; z-index: 4; }
.CodeMirror-lines { cursor: text; }
.CodeMirror pre { border-radius: 0px; border-width: 0px; background: 0px 0px; font-family: inherit; font-size: inherit; margin: 0px; white-space: pre; overflow-wrap: normal; color: inherit; z-index: 2; position: relative; overflow: visible; }
.CodeMirror-wrap pre { overflow-wrap: break-word; white-space: pre-wrap; word-break: normal; }
.CodeMirror-code pre { border-right: 30px solid transparent; width: fit-content; }
.CodeMirror-wrap .CodeMirror-code pre { border-right: none; width: auto; }
.CodeMirror-linebackground { position: absolute; inset: 0px; z-index: 0; }
.CodeMirror-linewidget { position: relative; z-index: 2; overflow: auto; }
.CodeMirror-wrap .CodeMirror-scroll { overflow-x: hidden; }
.CodeMirror-measure { position: absolute; width: 100%; height: 0px; overflow: hidden; visibility: hidden; }
.CodeMirror-measure pre { position: static; }
.CodeMirror div.CodeMirror-cursor { position: absolute; visibility: hidden; border-right: none; width: 0px; }
.CodeMirror div.CodeMirror-cursor { visibility: hidden; }
.CodeMirror-focused div.CodeMirror-cursor { visibility: inherit; }
.cm-searching { background: rgba(255, 255, 0, 0.4); }
span.cm-underlined { text-decoration: underline; }
span.cm-strikethrough { text-decoration: line-through; }
.cm-tw-syntaxerror { color: rgb(255, 255, 255); background-color: rgb(153, 0, 0); }
.cm-tw-deleted { text-decoration: line-through; }
.cm-tw-header5 { font-weight: 700; }
.cm-tw-listitem:first-child { padding-left: 10px; }
.cm-tw-box { border-style: solid; border-right-width: 1px; border-bottom-width: 1px; border-left-width: 1px; border-color: inherit; border-top-width: 0px !important; }
.cm-tw-underline { text-decoration: underline; }
@media print {
  .CodeMirror div.CodeMirror-cursor { visibility: hidden; }
}


:root {
    --side-bar-bg-color: #fafafa;
    --control-text-color: #777;
}

@include-when-export url(https://fonts.loli.net/css?family=Open+Sans:400italic,700italic,700,400&subset=latin,latin-ext);

/* open-sans-regular - latin-ext_latin */
  /* open-sans-italic - latin-ext_latin */
    /* open-sans-700 - latin-ext_latin */
    /* open-sans-700italic - latin-ext_latin */
  html {
    font-size: 16px;
    -webkit-font-smoothing: antialiased;
}

body {
    font-family: "Open Sans","Clear Sans", "Helvetica Neue", Helvetica, Arial, 'Segoe UI Emoji', sans-serif;
    color: rgb(51, 51, 51);
    line-height: 1.6;
}

#write {
    max-width: 860px;
  	margin: 0 auto;
  	padding: 30px;
    padding-bottom: 100px;
}

@media only screen and (min-width: 1400px) {
	#write {
		max-width: 1024px;
	}
}

@media only screen and (min-width: 1800px) {
	#write {
		max-width: 1200px;
	}
}

#write > ul:first-child,
#write > ol:first-child{
    margin-top: 30px;
}

a {
    color: #4183C4;
}
h1,
h2,
h3,
h4,
h5,
h6 {
    position: relative;
    margin-top: 1rem;
    margin-bottom: 1rem;
    font-weight: bold;
    line-height: 1.4;
    cursor: text;
}
h1:hover a.anchor,
h2:hover a.anchor,
h3:hover a.anchor,
h4:hover a.anchor,
h5:hover a.anchor,
h6:hover a.anchor {
    text-decoration: none;
}
h1 tt,
h1 code {
    font-size: inherit;
}
h2 tt,
h2 code {
    font-size: inherit;
}
h3 tt,
h3 code {
    font-size: inherit;
}
h4 tt,
h4 code {
    font-size: inherit;
}
h5 tt,
h5 code {
    font-size: inherit;
}
h6 tt,
h6 code {
    font-size: inherit;
}
h1 {
    font-size: 2.25em;
    line-height: 1.2;
    border-bottom: 1px solid #eee;
}
h2 {
    font-size: 1.75em;
    line-height: 1.225;
    border-bottom: 1px solid #eee;
}

/*@media print {
    .typora-export h1,
    .typora-export h2 {
        border-bottom: none;
        padding-bottom: initial;
    }

    .typora-export h1::after,
    .typora-export h2::after {
        content: "";
        display: block;
        height: 100px;
        margin-top: -96px;
        border-top: 1px solid #eee;
    }
}*/

h3 {
    font-size: 1.5em;
    line-height: 1.43;
}
h4 {
    font-size: 1.25em;
}
h5 {
    font-size: 1em;
}
h6 {
   font-size: 1em;
    color: #777;
}
p,
blockquote,
ul,
ol,
dl,
table{
    margin: 0.8em 0;
}
li>ol,
li>ul {
    margin: 0 0;
}
hr {
    height: 2px;
    padding: 0;
    margin: 16px 0;
    background-color: #e7e7e7;
    border: 0 none;
    overflow: hidden;
    box-sizing: content-box;
}

li p.first {
    display: inline-block;
}
ul,
ol {
    padding-left: 30px;
}
ul:first-child,
ol:first-child {
    margin-top: 0;
}
ul:last-child,
ol:last-child {
    margin-bottom: 0;
}
blockquote {
    border-left: 4px solid #dfe2e5;
    padding: 0 15px;
    color: #777777;
}
blockquote blockquote {
    padding-right: 0;
}
table {
    padding: 0;
    word-break: initial;
}
table tr {
    border: 1px solid #dfe2e5;
    margin: 0;
    padding: 0;
}
table tr:nth-child(2n),
thead {
    background-color: #f8f8f8;
}
table th {
    font-weight: bold;
    border: 1px solid #dfe2e5;
    border-bottom: 0;
    margin: 0;
    padding: 6px 13px;
}
table td {
    border: 1px solid #dfe2e5;
    margin: 0;
    padding: 6px 13px;
}
table th:first-child,
table td:first-child {
    margin-top: 0;
}
table th:last-child,
table td:last-child {
    margin-bottom: 0;
}

.CodeMirror-lines {
    padding-left: 4px;
}

.code-tooltip {
    box-shadow: 0 1px 1px 0 rgba(0,28,36,.3);
    border-top: 1px solid #eef2f2;
}

.md-fences,
code,
tt {
    border: 1px solid #e7eaed;
    background-color: #f8f8f8;
    border-radius: 3px;
    padding: 0;
    padding: 2px 4px 0px 4px;
    font-size: 0.9em;
}

code {
    background-color: #f3f4f4;
    padding: 0 2px 0 2px;
}

.md-fences {
    margin-bottom: 15px;
    margin-top: 15px;
    padding-top: 8px;
    padding-bottom: 6px;
}


.md-task-list-item > input {
  margin-left: -1.3em;
}

@media print {
    html {
        font-size: 13px;
    }
    table,
    pre {
        page-break-inside: avoid;
    }
    pre {
        word-wrap: break-word;
    }
}

.md-fences {
	background-color: #f8f8f8;
}
#write pre.md-meta-block {
	padding: 1rem;
    font-size: 85%;
    line-height: 1.45;
    background-color: #f7f7f7;
    border: 0;
    border-radius: 3px;
    color: #777777;
    margin-top: 0 !important;
}

.mathjax-block>.code-tooltip {
	bottom: .375rem;
}

.md-mathjax-midline {
    background: #fafafa;
}

#write>h3.md-focus:before{
	left: -1.5625rem;
	top: .375rem;
}
#write>h4.md-focus:before{
	left: -1.5625rem;
	top: .285714286rem;
}
#write>h5.md-focus:before{
	left: -1.5625rem;
	top: .285714286rem;
}
#write>h6.md-focus:before{
	left: -1.5625rem;
	top: .285714286rem;
}
.md-image>.md-meta {
    /*border: 1px solid #ddd;*/
    border-radius: 3px;
    padding: 2px 0px 0px 4px;
    font-size: 0.9em;
    color: inherit;
}

.md-tag {
    color: #a7a7a7;
    opacity: 1;
}

.md-toc { 
    margin-top:20px;
    padding-bottom:20px;
}

.sidebar-tabs {
    border-bottom: none;
}

#typora-quick-open {
    border: 1px solid #ddd;
    background-color: #f8f8f8;
}

#typora-quick-open-item {
    background-color: #FAFAFA;
    border-color: #FEFEFE #e5e5e5 #e5e5e5 #eee;
    border-style: solid;
    border-width: 1px;
}

/** focus mode */
.on-focus-mode blockquote {
    border-left-color: rgba(85, 85, 85, 0.12);
}

header, .context-menu, .megamenu-content, footer{
    font-family: "Segoe UI", "Arial", sans-serif;
}

.file-node-content:hover .file-node-icon,
.file-node-content:hover .file-node-open-state{
    visibility: visible;
}

.mac-seamless-mode #typora-sidebar {
    background-color: #fafafa;
    background-color: var(--side-bar-bg-color);
}

.md-lang {
    color: #b4654d;
}

/*.html-for-mac {
    --item-hover-bg-color: #E6F0FE;
}*/

#md-notification .btn {
    border: 0;
}

.dropdown-menu .divider {
    border-color: #e5e5e5;
    opacity: 0.4;
}

.ty-preferences .window-content {
    background-color: #fafafa;
}

.ty-preferences .nav-group-item.active {
    color: white;
    background: #999;
}

.menu-item-container a.menu-style-btn {
    background-color: #f5f8fa;
    background-image: linear-gradient( 180deg , hsla(0, 0%, 100%, 0.8), hsla(0, 0%, 100%, 0)); 
}



</style><title>C/C++基础合集：容器</title>
</head>
<body class='typora-export os-windows typora-export-show-outline typora-export-no-collapse-outline'><div class='typora-export-content'>
<div class="typora-export-sidebar"><div class="outline-content"><li class="outline-item-wrapper outline-h1"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#顺序容器">顺序容器</a></div><ul class="outline-children"><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#array">array</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#vector">vector</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#deque">deque</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#forwardlist">forward_list</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#list">list</a></div><ul class="outline-children"></ul></li></ul></li><li class="outline-item-wrapper outline-h1"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#关联容器">关联容器</a></div><ul class="outline-children"><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#set">set</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#map">map</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#multiset">multiset</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#mulitimap">mulitimap</a></div><ul class="outline-children"></ul></li></ul></li><li class="outline-item-wrapper outline-h1"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#无序关联容器">无序关联容器</a></div><ul class="outline-children"><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#unorderedset">unordered_set</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#unorderedmap">unordered_map</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#unorderedmultiset">unordered_multiset</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#unorderedmultimap">unordered_multimap</a></div><ul class="outline-children"></ul></li></ul></li><li class="outline-item-wrapper outline-h1"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#容器适配器">容器适配器</a></div><ul class="outline-children"><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#stack">stack</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#queue">queue</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h2"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#priorityqueue">priority_queue</a></div><ul class="outline-children"></ul></li></ul></li><li class="outline-item-wrapper outline-h1"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#span">span</a></div><ul class="outline-children"></ul></li><li class="outline-item-wrapper outline-h1"><div class="outline-item"><span class="outline-expander"></span><a class="outline-label" href="#迭代器">迭代器</a></div><ul class="outline-children"></ul></li></div></div><div id='write'  class=''><p><span>在c++中容器是STL中的重要内容，也是c++标准中重要的内容，所有的泛型通用算法其实都是基于容器与迭代器的，所以容器技术也成为c++的核心内容，也是本次准备秋招的重点部分。</span></p><p><span>容器库是类模板与算法的汇集，允许程序员简单地访问常见数据结构，例如队列、链表和栈。有三类容器——顺序容器、关联容器和无序关联容器——每种都被设计为支持不同组的操作。容器管理为其元素分配的存储空间，并提供直接或间接地通过迭代器（拥有类似指针属性的对象）访问它们的函数。大多数容器拥有至少几个常见的成员函数，并共享功能。特定应用的最佳容器不仅依赖于提供的功能，还依赖于对于不同工作量的效率。</span></p><div class='md-toc' mdtype='toc'><p class="md-toc-content" role="list"><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n5"><a class="md-toc-inner" href="#顺序容器">顺序容器</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n6"><a class="md-toc-inner" href="#array">array</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n13"><a class="md-toc-inner" href="#vector">vector</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n56"><a class="md-toc-inner" href="#deque">deque</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n74"><a class="md-toc-inner" href="#forwardlist">forward_list</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n80"><a class="md-toc-inner" href="#list">list</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n86"><a class="md-toc-inner" href="#关联容器">关联容器</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n87"><a class="md-toc-inner" href="#set">set</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n93"><a class="md-toc-inner" href="#map">map</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n99"><a class="md-toc-inner" href="#multiset">multiset</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n106"><a class="md-toc-inner" href="#mulitimap">mulitimap</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n113"><a class="md-toc-inner" href="#无序关联容器">无序关联容器</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n114"><a class="md-toc-inner" href="#unorderedset">unordered_set</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n115"><a class="md-toc-inner" href="#unorderedmap">unordered_map</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n116"><a class="md-toc-inner" href="#unorderedmultiset">unordered_multiset</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n117"><a class="md-toc-inner" href="#unorderedmultimap">unordered_multimap</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n118"><a class="md-toc-inner" href="#容器适配器">容器适配器</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n119"><a class="md-toc-inner" href="#stack">stack</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n120"><a class="md-toc-inner" href="#queue">queue</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n121"><a class="md-toc-inner" href="#priorityqueue">priority_queue</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n122"><a class="md-toc-inner" href="#span">span</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n123"><a class="md-toc-inner" href="#迭代器">迭代器</a></span></p></div><h1 id='顺序容器'><span>顺序容器</span></h1><h2 id='array'><span>array</span></h2><pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="c++"><div class="CodeMirror cm-s-inner cm-s-null-scroll CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.5px; left: 8px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 0px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: 0px; width: 0px;"></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;array&gt;</span></span></pre></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">template</span><span class="cm-operator">&lt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">T</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable">std::size_t</span> <span class="cm-variable">N</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-operator">&gt;</span> <span class="cm-keyword">struct</span> <span class="cm-def">array</span>;</span></pre></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 115px;"></div><div class="CodeMirror-gutters" style="display: none; height: 115px;"></div></div></div></pre><p>&nbsp;</p><p><code>std::array</code><span> 是封装固定大小数组的容器。此容器是一个聚合类型，其语义等同于保有一个 </span><a href='https://zh.cppreference.com/w/cpp/language/array'><span>C 风格数组</span></a><span> T[N] 作为其唯一非静态数据成员的结构体。不同于 C 风格数组，它不会自动退化成 </span><code>T*</code><span> 。它能作为聚合类型</span><a href='https://zh.cppreference.com/w/cpp/language/aggregate_initialization'><span>聚合初始化</span></a><span>，只要有至多 </span><code>N</code><span> 个能转换成 </span><code>T</code><span> 的初始化器：</span><code>std::array&lt;int, 3&gt; a = {1,2,3};</code><span>。该结构体结合了 C 风格数组的性能、可访问性与容器的优点，比如可获取大小、支持赋值、随机访问迭代器等。</span></p><p><code>std::array</code><span> 满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Container'><em><span>容器</span></em><span> </span><em><span>(Container)</span></em><span> </span></a><span>和</span><a href='https://zh.cppreference.com/w/cpp/named_req/ReversibleContainer'><em><span>可逆容器</span></em><span> </span><em><span>(ReversibleContainer)</span></em><span> </span></a><span>的要求，除了默认构造的 </span><code>array</code><span> 是非空的，以及进行交换的复杂度是线性，它满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/ContiguousContainer'><em><span>连续容器</span></em><span> </span><em><span>(ContiguousContainer)</span></em><span> </span></a><span>(C++17 起)的要求并部分满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/SequenceContainer'><em><span>序列容器</span></em><span> </span><em><span>(SequenceContainer)</span></em><span> </span></a><span>的要求。</span></p><p><span>当其长度为零时 </span><code>array</code><span> （ </span><code>N == 0</code><span> ）有特殊情况。此时， array.begin() == array.end() ，并拥有某个唯一值。在零长 </span><code>array</code><span> 上调用 </span><code>front()</code><span> 或 </span><code>back()</code><span> 是未定义的。亦可将 </span><code>array</code><span> 当做拥有 </span><code>N</code><span> 个同类型元素的元组。</span></p><p><span>按照规则，指向 </span><code>array</code><span> 的迭代器在 </span><code>array</code><span> 的生存期间决不非法化。然而要注意，在 </span><code>swap</code><span> 时，迭代器将继续指向同一 </span><code>array</code><span> 的元素，并将改变元素的值。</span></p><h2 id='vector'><span>vector</span></h2><pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="c++"><div class="CodeMirror cm-s-inner cm-s-null-scroll CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.5px; left: 8px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 0px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: 0px; width: 0px;"></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;vector&gt;</span></span></pre></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-comment">// std::vector 是封装动态数组的顺序容器。</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">template</span><span class="cm-operator">&lt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">T</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Allocator</span> <span class="cm-operator">=</span> <span class="cm-variable">std::allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-operator">&gt;</span> <span class="cm-keyword">class</span> <span class="cm-def">vector</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-comment">// std::pmr::vector 是使用多态分配器的模板别名。</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">namespace</span> <span class="cm-def">pmr</span> {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">template</span> <span class="cm-operator">&lt;</span><span class="cm-keyword">class</span> <span class="cm-def">T</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">using</span> <span class="cm-variable">vector</span> <span class="cm-operator">=</span> <span class="cm-variable">std::vector</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span>, <span class="cm-variable">std::pmr::polymorphic_allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span><span class="cm-operator">&gt;&gt;</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 299px;"></div><div class="CodeMirror-gutters" style="display: none; height: 299px;"></div></div></div></pre><p><span>元素相继存储，这意味着不仅可通过迭代器，还能用指向元素的常规指针访问元素。这意味着指向 </span><code>vector</code><span> 元素的指针能传递给任何期待指向数组元素的指针的函数。</span></p><p><code>vector</code><span> 的存储是自动管理的，按需扩张收缩。 </span><code>vector</code><span> 通常占用多于静态数组的空间，因为要分配更多内存以管理将来的增长。 </span><code>vector</code><span> 所用的方式不在每次插入元素时，而只在额外内存耗尽时重分配。分配的内存总量可用 </span><code>capacity()</code><span> 函数查询。额外内存可通过对 </span><code>shrink_to_fit()</code><span> 的调用返回给系统。 (C++11 起)</span></p><p><span>重分配通常是性能上有开销的操作。若元素数量已知，则 </span><code>reserve()</code><span> 函数可用于消除重分配。vector 上的常见操作复杂度（效率）如下：</span></p><ul><li><span>随机访问——常数 </span><em><span>O(1)</span></em></li><li><span>在末尾插入或移除元素——均摊常数 </span><em><span>O(1)</span></em></li><li><span>插入或移除元素——与到 vector 结尾的距离成线性 </span><em><span>O(n)</span></em></li></ul><p><code>std::vector</code><span> （对于 </span><code>bool</code><span> 以外的 </span><code>T</code><span> ）满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Container'><em><span>容器</span></em><span> </span><em><span>(Container)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AllocatorAwareContainer'><em><span>具分配器容器</span></em><span> </span><em><span>(AllocatorAwareContainer)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/SequenceContainer'><em><span>序列容器</span></em><span> </span><em><span>(SequenceContainer)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/ContiguousContainer'><em><span>连续容器</span></em><span> </span><em><span>(ContiguousContainer)</span></em><span> </span></a><span>(C++17 起)及</span><a href='https://zh.cppreference.com/w/cpp/named_req/ReversibleContainer'><em><span>可逆容器</span></em><span> </span><em><span>(ReversibleContainer)</span></em><span> </span></a><span>的要求。</span></p><p><span>模板参数：</span></p><ul><li><p><code>T</code><span>:  元素的类型。</span></p><ul><li><code>T</code><span> 必须满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/CopyAssignable'><em><span>可复制赋值</span></em><span> </span><em><span>(CopyAssignable)</span></em><span> </span></a><span>和</span><a href='https://zh.cppreference.com/w/cpp/named_req/CopyConstructible'><em><span>可复制构造</span></em><span> </span><em><span>(CopyConstructible)</span></em><span> </span></a><span>的要求。</span></li><li><span>加诸元素的要求依赖于容器上进行的实际操作。泛言之，要求元素类型是完整类型并满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Erasable'><em><span>可擦除</span></em><span> </span><em><span>(Erasable)</span></em><span> </span></a><span>的要求，但许多成员函数附带了更严格的要求。</span></li><li><span>加诸元素的要求依赖于容器上进行的实际操作。泛言之，要求元素类型满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Erasable'><em><span>可擦除</span></em><span> </span><em><span>(Erasable)</span></em><span> </span></a><span>的要求，但许多成员函数附带了更严格的要求。若分配器满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Allocator#.E5.88.86.E9.85.8D.E5.99.A8.E5.AE.8C.E6.95.B4.E6.80.A7.E8.A6.81.E6.B1.82'><span>分配器完整性要求</span></a><span>，则容器（但非其成员）能以不完整元素类型实例化。</span></li></ul></li><li><p><span>用于获取/释放内存及构造/析构内存中元素的分配器。类型必须满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Allocator'><em><span>分配器</span></em><span> </span><em><span>(Allocator)</span></em><span> </span></a><span>的要求。若 </span><code>Allocator::value_type</code><span> 与 </span><code>T</code><span> 不同则行为未定义。</span></p></li></ul><p><span>标准库提供 </span><code>std::vector</code><span> 对类型 </span><code>bool</code><span> 的特化，它可能为空间效率优化。</span></p><ol start='' ><li><p><span>vector底层原理，resize和reserve方法原理?</span></p><p><span>底层存储采用连续空间方式进行存储。</span></p></li></ol><ul><li><code>resize</code><span>重新申请并改变当前</span><code>vector</code><span>对象的有效空间大小，并可设置默认值；如果sz小于当等于前容量大小，则不改变容量大小，如果sz大于当前容量大小，则重新分配大小，容量等于sz；</span></li><li><code>reserve</code><span>:重新申请并改变当前</span><code>vector</code><span>对象的总空间（</span><code>_capacity</code><span>）大小，如果reserve的参数小于当等于当前size，则不会更改容量大小；</span></li></ul><ol start='2' ><li><p><span>C++ 的vector的底层数据结构是什么？为什么2倍扩容？</span></p><p><span>当数组大小不够容纳新增元素时，开辟更大的内存空间，把旧空间上的数据复制过来，然后在新空间中继续增加。新的更大的内存空间，一般是当前空间的1.5倍或者2倍，这个1.5或者2被称为扩容因子，不同系统实现扩容因子也不同。</span><strong><span>注意，扩容会导致迭代器失效。</span></strong></p><p><span>扩容因子越大，需要分配的新内存空间越多，越耗时。空闲空间较多，内存利用率低。</span></p><p><span>扩容因子越小，需要再分配的可能性就更高，多次扩容耗时。空闲空间较少，内存利用率高。</span></p><p><span>因此，小规模数组，添加元素不频繁的，建议使用扩容因子更小的。当数据规模越大，插入更频繁，大扩容因子更适合。</span></p></li></ol><h2 id='deque'><span>deque</span></h2><p><code>std::deque</code><span> （ double-ended queue ，双端队列）是有下标顺序容器，它允许在其首尾两段快速插入及删除。另外，在 </span><code>deque</code><span> 任一端插入或删除不会非法化指向其余元素的指针或引用。</span></p><p><span>与 </span><code>std::vector</code><span>相反， </span><code>deque</code><span> 的元素不是相接存储的：典型实现用单独分配的固定大小数组的序列，外加额外的登记，这表示下标访问必须进行二次指针解引用，与之相比 </span><code>vector</code><span> 的下标访问只进行一次。</span></p><p><code>deque</code><span> 的存储按需自动扩展及收缩。扩张 </span><code>deque</code><span> 比扩张 </span><code>std::vector</code><span> 更优，因为它不涉及到复制既存元素到新内存位置。另一方面， </span><code>deque</code><span> 典型地拥有较大的最小内存开销；只保有一个元素的 </span><code>deque</code><span> 必须分配其整个内部数组（例如 64 位 libstdc++ 上为对象大小 8 倍； 64 位 libc++ 上为对象大小 16 倍或 4096 字节的较大者）。</span></p><pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="c++"><div class="CodeMirror cm-s-inner cm-s-null-scroll CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.5px; left: 8px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 0px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: 0px; width: 0px;"></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;deque&gt;</span></span></pre></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">template</span><span class="cm-operator">&lt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">T</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Allocator</span> <span class="cm-operator">=</span> <span class="cm-variable">std::allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-operator">&gt;</span> <span class="cm-keyword">class</span> <span class="cm-def">deque</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">namespace</span> <span class="cm-def">pmr</span> {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">template</span> <span class="cm-operator">&lt;</span><span class="cm-keyword">class</span> <span class="cm-def">T</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">using</span> <span class="cm-variable">deque</span> <span class="cm-operator">=</span> <span class="cm-variable">std::deque</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span>, <span class="cm-variable">std::pmr::polymorphic_allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span><span class="cm-operator">&gt;&gt;</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 230px;"></div><div class="CodeMirror-gutters" style="display: none; height: 230px;"></div></div></div></pre><p><code>deque</code><span> 上常见操作的复杂度（效率）如下：</span></p><ul><li><span>随机访问——常数 </span><em><span>O(1)</span></em></li><li><span>在结尾或起始插入或移除元素——常数 </span><em><span>O(1)</span></em></li><li><span>插入或移除元素——线性 </span><em><span>O(n)</span></em></li></ul><p><code>std::deque</code><span> 满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Container'><em><span>容器</span></em><span> </span><em><span>(Container)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AllocatorAwareContainer'><em><span>具分配器容器</span></em><span> </span><em><span>(AllocatorAwareContainer)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/SequenceContainer'><em><span>序列容器</span></em><span> </span><em><span>(SequenceContainer)</span></em><span> </span></a><span>和</span><a href='https://zh.cppreference.com/w/cpp/named_req/ReversibleContainer'><em><span>可逆容器</span></em><span> </span><em><span>(ReversibleContainer)</span></em><span> </span></a><span>的要求。</span></p><p><span>双向队列的实现的核心是其迭代器的实现，下面是双向队列迭代器的实现形式，只有关键部分的代码。</span></p><p><img src="https://gitee.com/zyuegege/images/raw/master/imgs/IMG_20200616_101141.jpg" referrerpolicy="no-referrer" alt="img"></p><pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="c++" style="break-inside: unset;"><div class="CodeMirror cm-s-inner cm-s-null-scroll CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.5px; left: 8px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 0px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: 0px; width: 0px;"></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#define _GLIBCXX_DEQUE_BUF_SIZE 512 </span></span></pre></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-variable">_GLIBCXX_CONSTEXPR</span> <span class="cm-keyword">inline</span> <span class="cm-variable-3">size_t</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;<span class="cm-def">__deque_buf_size</span>(<span class="cm-variable-3">size_t</span> <span class="cm-variable">__size</span>)</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">  { <span class="cm-keyword">return</span> (<span class="cm-variable">__size</span> <span class="cm-operator">&lt;</span> <span class="cm-variable">_GLIBCXX_DEQUE_BUF_SIZE</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp; &nbsp;<span class="cm-operator">?</span> <span class="cm-variable-3">size_t</span>(<span class="cm-variable">_GLIBCXX_DEQUE_BUF_SIZE</span> <span class="cm-operator">/</span> <span class="cm-variable">__size</span>) : <span class="cm-variable-3">size_t</span>(<span class="cm-number">1</span>)); }</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">template</span><span class="cm-operator">&lt;</span><span class="cm-keyword">typename</span> <span class="cm-variable">_Tp</span>, <span class="cm-keyword">typename</span> <span class="cm-variable">_Ref</span>, <span class="cm-keyword">typename</span> <span class="cm-variable">_Ptr</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">struct</span> <span class="cm-def">_Deque_iterator</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;  {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">private</span>:</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">template</span><span class="cm-operator">&lt;</span><span class="cm-keyword">typename</span> <span class="cm-variable">_Up</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-keyword">using</span> <span class="cm-variable">__ptr_to</span> <span class="cm-operator">=</span> <span class="cm-keyword">typename</span> <span class="cm-variable">pointer_traits</span><span class="cm-operator">&lt;</span><span class="cm-variable">_Ptr</span><span class="cm-operator">&gt;</span>::<span class="cm-keyword">template</span> <span class="cm-variable">rebind</span><span class="cm-operator">&lt;</span><span class="cm-variable">_Up</span><span class="cm-operator">&gt;</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">template</span><span class="cm-operator">&lt;</span><span class="cm-keyword">typename</span> <span class="cm-variable">_CvTp</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-keyword">using</span> <span class="cm-variable">__iter</span> <span class="cm-operator">=</span> <span class="cm-variable">_Deque_iterator</span><span class="cm-operator">&lt;</span><span class="cm-variable">_Tp</span>, <span class="cm-variable">_CvTp</span><span class="cm-operator">&amp;</span>, <span class="cm-variable">__ptr_to</span><span class="cm-operator">&lt;</span><span class="cm-variable">_CvTp</span><span class="cm-operator">&gt;&gt;</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">public</span>:</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable">__iter</span><span class="cm-operator">&lt;</span><span class="cm-variable">_Tp</span><span class="cm-operator">&gt;</span><span class="cm-tab" role="presentation" cm-text="	">   </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">iterator</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable">__iter</span><span class="cm-operator">&lt;</span><span class="cm-keyword">const</span> <span class="cm-variable">_Tp</span><span class="cm-operator">&gt;</span><span class="cm-tab" role="presentation" cm-text="	"> </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">const_iterator</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable">__ptr_to</span><span class="cm-operator">&lt;</span><span class="cm-variable">_Tp</span><span class="cm-operator">&gt;</span><span class="cm-tab" role="presentation" cm-text="	"> </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">_Elt_pointer</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable">__ptr_to</span><span class="cm-operator">&lt;</span><span class="cm-variable">_Elt_pointer</span><span class="cm-operator">&gt;</span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">_Map_pointer</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> </span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">static</span> <span class="cm-variable-3">size_t</span> <span class="cm-variable">_S_buffer_size</span>() <span class="cm-variable">_GLIBCXX_NOEXCEPT</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;  { <span class="cm-keyword">return</span> <span class="cm-variable">__deque_buf_size</span>(<span class="cm-keyword">sizeof</span>(<span class="cm-variable">_Tp</span>)); } &nbsp; &nbsp; &nbsp; </span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable">std::random_access_iterator_tag</span><span class="cm-tab" role="presentation" cm-text="	">   </span><span class="cm-variable">iterator_category</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable">_Tp</span><span class="cm-tab" role="presentation" cm-text="	">   </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">value_type</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable">_Ptr</span><span class="cm-tab" role="presentation" cm-text="	">  </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">pointer</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable">_Ref</span><span class="cm-tab" role="presentation" cm-text="	">  </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">reference</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable-3">size_t</span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">size_type</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable-3">ptrdiff_t</span><span class="cm-tab" role="presentation" cm-text="	"> </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">difference_type</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">typedef</span> <span class="cm-variable">_Deque_iterator</span><span class="cm-tab" role="presentation" cm-text="	">   </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">_Self</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">_Elt_pointer</span> <span class="cm-variable">_M_cur</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">_Elt_pointer</span> <span class="cm-variable">_M_first</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">_Elt_pointer</span> <span class="cm-variable">_M_last</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">_Map_pointer</span> <span class="cm-variable">_M_node</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-comment">// 其他函数</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">_Self</span><span class="cm-operator">&amp;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">operator</span><span class="cm-operator">++</span>() <span class="cm-variable">_GLIBCXX_NOEXCEPT</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;  {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-operator">++</span><span class="cm-variable">_M_cur</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-keyword">if</span> (<span class="cm-variable">_M_cur</span> <span class="cm-operator">==</span> <span class="cm-variable">_M_last</span>)</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span>  {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp; &nbsp;<span class="cm-variable">_M_set_node</span>(<span class="cm-variable">_M_node</span> <span class="cm-operator">+</span> <span class="cm-number">1</span>);</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp; &nbsp;<span class="cm-variable">_M_cur</span> <span class="cm-operator">=</span> <span class="cm-variable">_M_first</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span>  }</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-keyword">return</span> <span class="cm-operator">*</span><span class="cm-keyword">this</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;  }</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">_Self</span><span class="cm-operator">&amp;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">operator</span><span class="cm-operator">--</span>() <span class="cm-variable">_GLIBCXX_NOEXCEPT</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;  {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-keyword">if</span> (<span class="cm-variable">_M_cur</span> <span class="cm-operator">==</span> <span class="cm-variable">_M_first</span>)</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span>  {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp; &nbsp;<span class="cm-variable">_M_set_node</span>(<span class="cm-variable">_M_node</span> <span class="cm-operator">-</span> <span class="cm-number">1</span>);</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp; &nbsp;<span class="cm-variable">_M_cur</span> <span class="cm-operator">=</span> <span class="cm-variable">_M_last</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span>  }</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-operator">--</span><span class="cm-variable">_M_cur</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-keyword">return</span> <span class="cm-operator">*</span><span class="cm-keyword">this</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;  }</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-comment">/**</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; <span class="cm-comment">*  Prepares to traverse new_node.  Sets everything except</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; <span class="cm-comment">*  _M_cur, which should therefore be set by the caller</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; <span class="cm-comment">*  immediately afterwards, based on _M_first and _M_last.</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; <span class="cm-comment">*/</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable-3">void</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">_M_set_node</span>(<span class="cm-variable">_Map_pointer</span> <span class="cm-variable">__new_node</span>) <span class="cm-variable">_GLIBCXX_NOEXCEPT</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;  {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">_M_node</span> <span class="cm-operator">=</span> <span class="cm-variable">__new_node</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">_M_first</span> <span class="cm-operator">=</span> <span class="cm-operator">*</span><span class="cm-variable">__new_node</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">_M_last</span> <span class="cm-operator">=</span> <span class="cm-variable">_M_first</span> <span class="cm-operator">+</span> <span class="cm-variable">difference_type</span>(<span class="cm-variable">_S_buffer_size</span>());</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;  }</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;  }</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-comment">//This struct encapsulates the implementation of the std::deque</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-comment">//standard container and at the same time makes use of the EBO</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-comment">//for empty allocators.</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">struct</span> <span class="cm-def">_Deque_impl</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;  : <span class="cm-keyword">public</span> <span class="cm-variable">_Tp_alloc_type</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;  {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">_Map_pointer</span> <span class="cm-variable">_M_map</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable-3">size_t</span> <span class="cm-variable">_M_map_size</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">iterator</span> <span class="cm-variable">_M_start</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-variable">iterator</span> <span class="cm-variable">_M_finish</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;  };</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;<span class="cm-comment">/**</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; <span class="cm-comment">*  @brief Layout storage.</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; <span class="cm-comment">*  @param  __num_elements  The count of T's for which to allocate space</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; <span class="cm-comment">* &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  at first.</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; <span class="cm-comment">*  @return &nbsp; Nothing.</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; <span class="cm-comment">*</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; <span class="cm-comment">*  The initial underlying memory layout is a bit complicated...</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;<span class="cm-comment">*/</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;<span class="cm-keyword">template</span><span class="cm-operator">&lt;</span><span class="cm-keyword">typename</span> <span class="cm-variable">_Tp</span>, <span class="cm-keyword">typename</span> <span class="cm-variable">_Alloc</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable-3">void</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable">_Deque_base</span><span class="cm-operator">&lt;</span><span class="cm-variable">_Tp</span>, <span class="cm-variable">_Alloc</span><span class="cm-operator">&gt;</span>::</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-variable">_M_initialize_map</span>(<span class="cm-variable-3">size_t</span> <span class="cm-variable">__num_elements</span>)</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;  {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">const</span> <span class="cm-variable-3">size_t</span> <span class="cm-variable">__num_nodes</span> <span class="cm-operator">=</span> (<span class="cm-variable">__num_elements</span><span class="cm-operator">/</span> <span class="cm-variable">__deque_buf_size</span>(<span class="cm-keyword">sizeof</span>(<span class="cm-variable">_Tp</span>))</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp;<span class="cm-operator">+</span> <span class="cm-number">1</span>);</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_map_size</span> <span class="cm-operator">=</span> <span class="cm-variable">std::max</span>((<span class="cm-variable-3">size_t</span>) <span class="cm-variable">_S_initial_map_size</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp; <span class="cm-variable-3">size_t</span>(<span class="cm-variable">__num_nodes</span> <span class="cm-operator">+</span> <span class="cm-number">2</span>));</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_map</span> <span class="cm-operator">=</span> <span class="cm-variable">_M_allocate_map</span>(<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_map_size</span>);</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-comment">// For "small" maps (needing less than _M_map_size nodes), allocation</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-comment">// starts in the middle elements and grows outwards.  So nstart may be</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-comment">// the beginning of _M_map, but for small maps it may be as far in as</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-comment">// _M_map+3.</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">_Map_pointer</span> <span class="cm-variable">__nstart</span> <span class="cm-operator">=</span> (<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_map</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp; &nbsp; &nbsp; <span class="cm-operator">+</span> (<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_map_size</span> <span class="cm-operator">-</span> <span class="cm-variable">__num_nodes</span>) <span class="cm-operator">/</span> <span class="cm-number">2</span>);</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">_Map_pointer</span> <span class="cm-variable">__nfinish</span> <span class="cm-operator">=</span> <span class="cm-variable">__nstart</span> <span class="cm-operator">+</span> <span class="cm-variable">__num_nodes</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">__try</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span>{ <span class="cm-variable">_M_create_nodes</span>(<span class="cm-variable">__nstart</span>, <span class="cm-variable">__nfinish</span>); }</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-variable">__catch</span>(...)</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span>{</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp;<span class="cm-variable">_M_deallocate_map</span>(<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_map</span>, <span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_map_size</span>);</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp;<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_map</span> <span class="cm-operator">=</span> <span class="cm-variable">_Map_pointer</span>();</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp;<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_map_size</span> <span class="cm-operator">=</span> <span class="cm-number">0</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span> &nbsp;<span class="cm-variable">__throw_exception_again</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span>}</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_start</span>.<span class="cm-variable">_M_set_node</span>(<span class="cm-variable">__nstart</span>);</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_finish</span>.<span class="cm-variable">_M_set_node</span>(<span class="cm-variable">__nfinish</span> <span class="cm-operator">-</span> <span class="cm-number">1</span>);</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_start</span>.<span class="cm-variable">_M_cur</span> <span class="cm-operator">=</span> <span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_start</span>.<span class="cm-variable">_M_first</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp;<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_finish</span>.<span class="cm-variable">_M_cur</span> <span class="cm-operator">=</span> (<span class="cm-keyword">this</span><span class="cm-operator">-&gt;</span><span class="cm-variable">_M_impl</span>.<span class="cm-variable">_M_finish</span>.<span class="cm-variable">_M_first</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-operator">+</span> <span class="cm-variable">__num_elements</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-tab" role="presentation" cm-text="	">    </span><span class="cm-operator">%</span> <span class="cm-variable">__deque_buf_size</span>(<span class="cm-keyword">sizeof</span>(<span class="cm-variable">_Tp</span>)));</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp;  } &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 3174px;"></div><div class="CodeMirror-gutters" style="display: none; height: 3174px;"></div></div></div></pre><p>&nbsp;</p><h2 id='forwardlist'><span>forward_list</span></h2><p><code>std::forward_list</code><span> 是支持从容器中的任何位置快速插入和移除元素的容器。不支持快速随机访问。它实现为单链表，且实质上与其在 C 中实现相比无任何开销。与 </span><code>std::list</code><span>相比，此容器在不需要双向迭代时提供更有效地利用空间的存储。</span></p><p><span>在链表内或跨数个链表添加、移除和移动元素，不会非法化当前指代链表中其他元素的迭代器。然而，在从链表移除元素（通过 </span><a href='https://zh.cppreference.com/w/cpp/container/forward_list/erase_after'><span>erase_after</span></a><span> ）时，指代对应元素的迭代器或引用会被非法化。</span></p><p><code>std::forward_list</code><span> 满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Container'><em><span>容器</span></em><span> </span><em><span>(Container)</span></em><span> </span></a><span>（除了 </span><code>operator==</code><span> 的复杂度始终为线性和 </span><code>size</code><span> 函数）、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AllocatorAwareContainer'><em><span>具分配器容器</span></em><span> </span><em><span>(AllocatorAwareContainer)</span></em><span> </span></a><span>和</span><a href='https://zh.cppreference.com/w/cpp/named_req/SequenceContainer'><em><span>序列容器</span></em><span> </span><em><span>(SequenceContainer)</span></em><span> </span></a><span>的要求。</span></p><pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="c++"><div class="CodeMirror cm-s-inner cm-s-null-scroll CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.5px; left: 8px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 0px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: 0px; width: 0px;"></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;forward_list&gt;</span></span></pre></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">template</span><span class="cm-operator">&lt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">T</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Allocator</span> <span class="cm-operator">=</span> <span class="cm-variable">std::allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-operator">&gt;</span> <span class="cm-keyword">class</span> <span class="cm-def">forward_list</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">namespace</span> <span class="cm-def">pmr</span> {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">template</span> <span class="cm-operator">&lt;</span><span class="cm-keyword">class</span> <span class="cm-def">T</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">using</span> <span class="cm-variable">forward_list</span> <span class="cm-operator">=</span> <span class="cm-variable">std::forward_list</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span>, <span class="cm-variable">std::pmr::polymorphic_allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span><span class="cm-operator">&gt;&gt;</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 230px;"></div><div class="CodeMirror-gutters" style="display: none; height: 230px;"></div></div></div></pre><p>&nbsp;</p><h2 id='list'><span>list</span></h2><p><code>std::list</code><span> 是支持常数时间从容器任何位置插入和移除元素的容器。不支持快速随机访问。它通常实现为双向链表。与 </span><code>std::forward_list</code><span>相比，此容器提供双向迭代但在空间上效率稍低。</span></p><p><span>在 </span><code>list</code><span> 内或在数个 </span><code>list</code><span> 间添加、移除和移动元素不会非法化迭代器或引用。迭代器仅在对应元素被删除时非法化。</span></p><p><code>std::list</code><span> 满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Container'><em><span>容器</span></em><span> </span><em><span>(Container)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AllocatorAwareContainer'><em><span>具分配器容器</span></em><span> </span><em><span>(AllocatorAwareContainer)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/SequenceContainer'><em><span>序列容器</span></em><span> </span><em><span>(SequenceContainer)</span></em><span> </span></a><span>及</span><a href='https://zh.cppreference.com/w/cpp/named_req/ReversibleContainer'><em><span>可逆容器</span></em><span> </span><em><span>(ReversibleContainer)</span></em><span> </span></a><span>的要求。</span></p><pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="c++"><div class="CodeMirror cm-s-inner cm-s-null-scroll CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.5px; left: 8px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 0px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: 0px; width: 0px;"></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;list&gt;</span></span></pre></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">template</span><span class="cm-operator">&lt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">T</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Allocator</span> <span class="cm-operator">=</span> <span class="cm-variable">std::allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-operator">&gt;</span> <span class="cm-keyword">class</span> <span class="cm-def">list</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">namespace</span> <span class="cm-def">pmr</span> {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">template</span> <span class="cm-operator">&lt;</span><span class="cm-keyword">class</span> <span class="cm-def">T</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">using</span> <span class="cm-variable">list</span> <span class="cm-operator">=</span> <span class="cm-variable">std::list</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span>, <span class="cm-variable">std::pmr::polymorphic_allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">T</span><span class="cm-operator">&gt;&gt;</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 253px;"></div><div class="CodeMirror-gutters" style="display: none; height: 253px;"></div></div></div></pre><p>&nbsp;</p><h1 id='关联容器'><span>关联容器</span></h1><h2 id='set'><span>set</span></h2><p><code>std::set</code><span> 是关联容器，含有 </span><code>Key</code><span> 类型对象的已排序集。用比较函数 </span><a href='https://zh.cppreference.com/w/cpp/named_req/Compare'><em><span>比较</span></em><span> </span><em><span>(Compare)</span></em><span> </span></a><span>进行排序。搜索、移除和插入拥有对数复杂度。 </span><code>set</code><span> 通常以</span><a href='https://en.wikipedia.org/wiki/Red–black_tree'><span>红黑树</span></a><span>实现。</span></p><p><span>在每个标准库使用</span><a href='https://zh.cppreference.com/w/cpp/named_req/Compare'><em><span>比较</span></em><span> </span><em><span>(Compare)</span></em><span> </span></a><span>概念的场所，用等价关系确定唯一性。不精确地说，若二个对象 </span><code>a</code><span> 与 </span><code>b</code><span> 相互间既不比较大于亦不比较小于： </span><code>!comp(a, b) &amp;&amp; !comp(b, a)</code><span> ，则认为它们等价。</span></p><p><code>std::set</code><span> 满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Container'><em><span>容器</span></em><span> </span><em><span>(Container)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AllocatorAwareContainer'><em><span>具分配器容器</span></em><span> </span><em><span>(AllocatorAwareContainer)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AssociativeContainer'><em><span>关联容器</span></em><span> </span><em><span>(AssociativeContainer)</span></em><span> </span></a><span>和</span><a href='https://zh.cppreference.com/w/cpp/named_req/ReversibleContainer'><em><span>可逆容器</span></em><span> </span><em><span>(ReversibleContainer)</span></em><span> </span></a><span>的要求。</span></p><pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="c++"><div class="CodeMirror cm-s-inner cm-s-null-scroll CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.5px; left: 8px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 0px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: 0px; width: 0px;"></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;set&gt;</span></span></pre></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">template</span><span class="cm-operator">&lt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Key</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Compare</span> <span class="cm-operator">=</span> <span class="cm-variable">std::less</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Allocator</span> <span class="cm-operator">=</span> <span class="cm-variable">std::allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-operator">&gt;</span> <span class="cm-keyword">class</span> <span class="cm-def">set</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">namespace</span> <span class="cm-def">pmr</span> {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">template</span> <span class="cm-operator">&lt;</span><span class="cm-keyword">class</span> <span class="cm-def">Key</span>, <span class="cm-keyword">class</span> <span class="cm-def">Compare</span> <span class="cm-operator">=</span> <span class="cm-variable">std::less</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">using</span> <span class="cm-variable">set</span> <span class="cm-operator">=</span> <span class="cm-variable">std::set</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span>, <span class="cm-variable">Compare</span>, <span class="cm-variable">std::pmr::polymorphic_allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;&gt;</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 276px;"></div><div class="CodeMirror-gutters" style="display: none; height: 276px;"></div></div></div></pre><p>&nbsp;</p><h2 id='map'><span>map</span></h2><p><code>std::map</code><span> 是有序键值对容器，它的元素的键是唯一的。用比较函数 </span><code>Compare</code><span> 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为</span><a href='https://en.wikipedia.org/wiki/Red–black_tree'><span>红黑树</span></a><span>。</span></p><p><span>在每个标准库使用</span><a href='https://zh.cppreference.com/w/cpp/named_req/Compare'><em><span>比较</span></em><span> </span><em><span>(Compare)</span></em><span> </span></a><span>概念的位置，以等价关系检验唯一性。不精确而言，若二个对象 </span><code>a</code><span> 与 </span><code>b</code><span> 互相比较不小于对方 ： </span><code>!comp(a, b) &amp;&amp; !comp(b, a)</code><span> ，则认为它们等价（非唯一）。</span></p><p><code>std::map</code><span> 满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Container'><em><span>容器</span></em><span> </span><em><span>(Container)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AllocatorAwareContainer'><em><span>具分配器容器</span></em><span> </span><em><span>(AllocatorAwareContainer)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AssociativeContainer'><em><span>关联容器</span></em><span> </span><em><span>(AssociativeContainer)</span></em><span> </span></a><span>和</span><a href='https://zh.cppreference.com/w/cpp/named_req/ReversibleContainer'><em><span>可逆容器</span></em><span> </span><em><span>(ReversibleContainer)</span></em><span> </span></a><span>的要求。</span></p><pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="c++" style="break-inside: unset;"><div class="CodeMirror cm-s-inner cm-s-null-scroll CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.5px; left: 8px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 0px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: 0px; width: 0px;"></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;map&gt;</span></span></pre></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">template</span><span class="cm-operator">&lt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Key</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">T</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Compare</span> <span class="cm-operator">=</span> <span class="cm-variable">std::less</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Allocator</span> <span class="cm-operator">=</span> <span class="cm-variable">std::allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">std::pair</span><span class="cm-operator">&lt;</span><span class="cm-keyword">const</span> <span class="cm-variable">Key</span>, <span class="cm-variable">T</span><span class="cm-operator">&gt;</span> <span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-operator">&gt;</span> <span class="cm-keyword">class</span> <span class="cm-def">map</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">namespace</span> <span class="cm-def">pmr</span> {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">template</span> <span class="cm-operator">&lt;</span><span class="cm-keyword">class</span> <span class="cm-def">Key</span>, <span class="cm-keyword">class</span> <span class="cm-def">T</span>, <span class="cm-keyword">class</span> <span class="cm-def">Compare</span> <span class="cm-operator">=</span> <span class="cm-variable">std::less</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">using</span> <span class="cm-variable">map</span> <span class="cm-operator">=</span> <span class="cm-variable">std::map</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span>, <span class="cm-variable">T</span>, <span class="cm-variable">Compare</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="cm-variable">std::pmr::polymorphic_allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">std::pair</span><span class="cm-operator">&lt;</span><span class="cm-keyword">const</span> <span class="cm-variable">Key</span>,<span class="cm-variable">T</span><span class="cm-operator">&gt;&gt;&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 322px;"></div><div class="CodeMirror-gutters" style="display: none; height: 322px;"></div></div></div></pre><p>&nbsp;</p><h2 id='multiset'><span>multiset</span></h2><p><code>std::multiset</code><span> 是含有 Key 类型对象有序集的容器。不同于 set ，它允许多个关键拥有等价的值。用关键比较函数 Compare 进行排序。搜索、插入和移除操作拥有对数复杂度。</span></p><p><span>在标准库使用</span><a href='https://zh.cppreference.com/w/cpp/named_req/Compare'><em><span>比较</span></em><span> </span><em><span>(Compare)</span></em><span> </span></a><span>概念的每处，都用描述于</span><a href='https://zh.cppreference.com/w/cpp/named_req/Compare'><em><span>比较</span></em><span> </span><em><span>(Compare)</span></em><span> </span></a><span>的等价关系确定等价性。不精确地说，若二个对象 </span><code>a</code><span> 和 </span><code>b</code><span> 互不比较小于对方： </span><code>!comp(a, b) &amp;&amp; !comp(b, a)</code><span> ，则认为它们等价。</span></p><p><span>比较等价的元素顺序是插入顺序，而且不会更改。(C++11 起)</span></p><p><code>std::multiset</code><span> 满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Container'><em><span>容器</span></em><span> </span><em><span>(Container)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AllocatorAwareContainer'><em><span>具分配器容器</span></em><span> </span><em><span>(AllocatorAwareContainer)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AssociativeContainer'><em><span>关联容器</span></em><span> </span><em><span>(AssociativeContainer)</span></em><span> </span></a><span>和</span><a href='https://zh.cppreference.com/w/cpp/named_req/ReversibleContainer'><em><span>可逆容器</span></em><span> </span><em><span>(ReversibleContainer)</span></em><span> </span></a><span>的要求。</span></p><pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="c++"><div class="CodeMirror cm-s-inner cm-s-null-scroll CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.5px; left: 8px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 0px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: 0px; width: 0px;"></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;set&gt;</span></span></pre></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">template</span><span class="cm-operator">&lt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Key</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Compare</span> <span class="cm-operator">=</span> <span class="cm-variable">std::less</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Allocator</span> <span class="cm-operator">=</span> <span class="cm-variable">std::allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-operator">&gt;</span> <span class="cm-keyword">class</span> <span class="cm-def">multiset</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">namespace</span> <span class="cm-def">pmr</span> {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">template</span> <span class="cm-operator">&lt;</span><span class="cm-keyword">class</span> <span class="cm-def">Key</span>, <span class="cm-keyword">class</span> <span class="cm-def">Compare</span> <span class="cm-operator">=</span> <span class="cm-variable">std::less</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">using</span> <span class="cm-variable">multiset</span> <span class="cm-operator">=</span> <span class="cm-variable">std::multiset</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span>, <span class="cm-variable">Compare</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="cm-variable">std::pmr::polymorphic_allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;&gt;</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 299px;"></div><div class="CodeMirror-gutters" style="display: none; height: 299px;"></div></div></div></pre><p>&nbsp;</p><h2 id='mulitimap'><span>mulitimap</span></h2><p><span>multimap 是关联容器，含有键值对的已排序列表，同时容许多个元素拥有同一键。按照应用到键的比较函数 </span><code>Compare</code><span> 排序。搜索、插入和移除操作拥有对数复杂度。</span></p><p><span>拥有等价键的键值对的顺序就是插入顺序，且不会更改。(C++11 起)</span></p><p><span>凡在标准库使用</span><a href='https://zh.cppreference.com/w/cpp/named_req/Compare'><em><span>比较</span></em><span> </span><em><span>(Compare)</span></em><span> </span></a><span>概念出，都用描述于</span><a href='https://zh.cppreference.com/w/cpp/named_req/Compare'><em><span>比较</span></em><span> </span><em><span>(Compare)</span></em><span> </span></a><span>上的等价关系确定等价性。不精确地说，若二个对象 </span><code>a</code><span> 和 </span><code>b</code><span> 互不小于对方： </span><code>!comp(a, b) &amp;&amp; !comp(b, a)</code><span> ，则认为它们等价。</span></p><p><code>std::multimap</code><span> 满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/Container'><em><span>容器</span></em><span> </span><em><span>(Container)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AllocatorAwareContainer'><em><span>具分配器容器</span></em><span> </span><em><span>(AllocatorAwareContainer)</span></em><span> </span></a><span>、</span><a href='https://zh.cppreference.com/w/cpp/named_req/AssociativeContainer'><em><span>关联容器</span></em><span> </span><em><span>(AssociativeContainer)</span></em><span> </span></a><span>和</span><a href='https://zh.cppreference.com/w/cpp/named_req/ReversibleContainer'><em><span>可逆容器</span></em><span> </span><em><span>(ReversibleContainer)</span></em><span> </span></a><span>的要求。</span></p><pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="c++" style="break-inside: unset;"><div class="CodeMirror cm-s-inner cm-s-null-scroll CodeMirror-wrap" lang="c++"><div style="overflow: hidden; position: relative; width: 3px; height: 0px; top: 9.5px; left: 8px;"><textarea autocorrect="off" autocapitalize="off" spellcheck="false" tabindex="0" style="position: absolute; bottom: -1em; padding: 0px; width: 1000px; height: 1em; outline: none;"></textarea></div><div class="CodeMirror-scrollbar-filler" cm-not-content="true"></div><div class="CodeMirror-gutter-filler" cm-not-content="true"></div><div class="CodeMirror-scroll" tabindex="-1"><div class="CodeMirror-sizer" style="margin-left: 0px; margin-bottom: 0px; border-right-width: 0px; padding-right: 0px; padding-bottom: 0px;"><div style="position: relative; top: 0px;"><div class="CodeMirror-lines" role="presentation"><div role="presentation" style="position: relative; outline: none;"><div class="CodeMirror-measure"><pre><span>xxxxxxxxxx</span></pre></div><div class="CodeMirror-measure"></div><div style="position: relative; z-index: 1;"></div><div class="CodeMirror-code" role="presentation" style=""><div class="CodeMirror-activeline" style="position: relative;"><div class="CodeMirror-activeline-background CodeMirror-linebackground"></div><div class="CodeMirror-gutter-background CodeMirror-activeline-gutter" style="left: 0px; width: 0px;"></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-meta">#include &lt;map&gt;</span></span></pre></div><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">template</span><span class="cm-operator">&lt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Key</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">T</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Compare</span> <span class="cm-operator">=</span> <span class="cm-variable">std::less</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">class</span> <span class="cm-def">Allocator</span> <span class="cm-operator">=</span> <span class="cm-variable">std::allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">std::pair</span><span class="cm-operator">&lt;</span><span class="cm-keyword">const</span> <span class="cm-variable">Key</span>, <span class="cm-variable">T</span><span class="cm-operator">&gt;</span> <span class="cm-operator">&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-operator">&gt;</span> <span class="cm-keyword">class</span> <span class="cm-def">multimap</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span cm-text="" cm-zwsp="">
</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"><span class="cm-keyword">namespace</span> <span class="cm-def">pmr</span> {</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">template</span> <span class="cm-operator">&lt;</span><span class="cm-keyword">class</span> <span class="cm-def">Key</span>, <span class="cm-keyword">class</span> <span class="cm-def">T</span>, <span class="cm-keyword">class</span> <span class="cm-def">Compare</span> <span class="cm-operator">=</span> <span class="cm-variable">std::less</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span><span class="cm-operator">&gt;&gt;</span></span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp;<span class="cm-keyword">using</span> <span class="cm-variable">multimap</span> <span class="cm-operator">=</span> <span class="cm-variable">std::multimap</span><span class="cm-operator">&lt;</span><span class="cm-variable">Key</span>, <span class="cm-variable">T</span>, <span class="cm-variable">Compare</span>,</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="cm-variable">std::pmr::polymorphic_allocator</span><span class="cm-operator">&lt;</span><span class="cm-variable">std::pair</span><span class="cm-operator">&lt;</span><span class="cm-keyword">const</span> <span class="cm-variable">Key</span>,<span class="cm-variable">T</span><span class="cm-operator">&gt;&gt;&gt;</span>;</span></pre><pre class=" CodeMirror-line " role="presentation"><span role="presentation" style="padding-right: 0.1px;">}</span></pre></div></div></div></div></div><div style="position: absolute; height: 0px; width: 1px; border-bottom: 0px solid transparent; top: 322px;"></div><div class="CodeMirror-gutters" style="display: none; height: 322px;"></div></div></div></pre><p>&nbsp;</p><h1 id='无序关联容器'><span>无序关联容器</span></h1><h2 id='unorderedset'><span>unordered_set</span></h2><h2 id='unorderedmap'><span>unordered_map</span></h2><h2 id='unorderedmultiset'><span>unordered_multiset</span></h2><h2 id='unorderedmultimap'><span>unordered_multimap</span></h2><h1 id='容器适配器'><span>容器适配器</span></h1><h2 id='stack'><span>stack</span></h2><h2 id='queue'><span>queue</span></h2><h2 id='priorityqueue'><span>priority_queue</span></h2><h1 id='span'><span>span</span></h1><h1 id='迭代器'><span>迭代器</span></h1><p><span>遗留输入迭代器 (LegacyInputIterator) 、遗留输出迭代器 (LegacyOutputIterator) 、遗留向前迭代器 (LegacyForwardIterator) 、遗留双向迭代器 (LegacyBidirectionalIterator) 、遗留随机访问迭代器 (LegacyRandomAccessIterator) ，及遗留连续迭代器 (LegacyContiguousIterator) (C++17 起)。</span></p><p><span>迭代器的分类的依据并不是迭代器的类型，而是迭代器所支持的操作。换句话说，某个类型只要支持相应的操作，就可以作为迭代器使用。例如，完整对象类型指针支持所有</span><a href='https://zh.cppreference.com/w/cpp/named_req/RandomAccessIterator'><em><span>遗留随机访问迭代器</span></em><span> </span><em><span>(LegacyRandomAccessIterator)</span></em><span> </span></a><span>要求的操作，于是任何需要</span><a href='https://zh.cppreference.com/w/cpp/named_req/RandomAccessIterator'><em><span>遗留随机访问迭代器</span></em><span> </span><em><span>(LegacyRandomAccessIterator)</span></em><span> </span></a><span>的地方都可以使用指针。</span></p><p><span>迭代器的所有类别（除了</span><a href='https://zh.cppreference.com/w/cpp/named_req/OutputIterator'><em><span>遗留输出迭代器</span></em><span> </span><em><span>(LegacyOutputIterator)</span></em><span> </span></a><span>和</span><a href='https://zh.cppreference.com/w/cpp/named_req/ContiguousIterator'><em><span>遗留连续迭代器</span></em><span> </span><em><span>(LegacyContiguousIterator)</span></em><span> </span></a><span>）能组织到层级中，其中更强力的迭代器类别（如</span><a href='https://zh.cppreference.com/w/cpp/named_req/RandomAccessIterator'><em><span>遗留随机访问迭代器</span></em><span> </span><em><span>(LegacyRandomAccessIterator)</span></em><span> </span></a><span>）支持较不强力的类别（例如</span><a href='https://zh.cppreference.com/w/cpp/named_req/InputIterator'><em><span>遗留输入迭代器</span></em><span> </span><em><span>(LegacyInputIterator)</span></em><span> </span></a><span>）的所有操作。若迭代器落入这些类别之一且亦满足</span><a href='https://zh.cppreference.com/w/cpp/named_req/OutputIterator'><em><span>遗留输出迭代器</span></em><span> </span><em><span>(LegacyOutputIterator)</span></em><span> </span></a><span>的要求，则称之为</span><em><span>可变</span></em><span> 迭代器并且支持输入</span><em><span>还有</span></em><span>输出。称非可变迭代器为</span><em><span>常</span></em><span>迭代器。</span></p><p>&nbsp;</p></div></div>

<script>(function(){var e=document.body.parentElement,t=[],n=null,i=document.body.classList.contains("typora-export-collapse-outline"),r=function(e,t,n){document.addEventListener(e,function(e){if(!e.defaultPrevented)for(var i=e.target;i&&i!=this;i=i.parentNode)if(i.matches(t)){!1===n.call(i,e)&&(e.preventDefault(),e.stopPropagation());break}},!1)};function o(){return e.scrollTop}r("click",".outline-expander",function(e){var t=this.closest(".outline-item-wrapper").classList;return t.contains("outline-item-open")?t.remove("outline-item-open"):t.add("outline-item-open"),d(),!1}),r("click",".outline-item",function(e){var t=this.querySelector(".outline-label");if(location.hash="#"+t.getAttribute("href"),i){var n=this.closest(".outline-item-wrapper").classList;n.contains("outline-item-open")||n.add("outline-item-open"),c(),n.add("outline-item-active")}});var a,s,l=function(){var e=o();n=null;for(var i=0;i<t.length&&t[i][1]-e<60;i++)n=t[i]},c=function(){document.querySelectorAll(".outline-item-active").forEach(e=>e.classList.remove("outline-item-active")),document.querySelectorAll(".outline-item-single.outline-item-open").forEach(e=>e.classList.remove("outline-item-open"))},d=function(){if(n){c();var e=document.querySelector('.outline-label[href="#'+(CSS.escape?CSS.escape(n[0]):n[0])+'"]');if(e)if(i){var t=e.closest(".outline-item-open>ul>.outline-item-wrapper");if(t)t.classList.add("outline-item-active");else{for(var r=(e=e.closest(".outline-item-wrapper")).parentElement.closest(".outline-item-wrapper");r;)r=(e=r).parentElement.closest(".outline-item-wrapper");e.classList.add("outline-item-active")}}else e.closest(".outline-item-wrapper").classList.add("outline-item-active")}};window.addEventListener("scroll",function(e){a&&clearTimeout(a),a=setTimeout(function(){l(),d()},300)});var u=function(){s=setTimeout(function(){!function(){t=[];var e=o();document.querySelector("#write").querySelectorAll("h1, h2, h3, h4, h5, h6").forEach(n=>{var i=n.getAttribute("id");t.push([i,e+n.getBoundingClientRect().y])})}(),l(),d()},300)};window.addEventListener("resize",function(e){s&&clearTimeout(s),u()}),u()})();</script><script src="/js/typora-convert.js"></script>
</body>
</html>